public class Sort {
    /**
     * 计数排序,一种不用比较的方法
     */
    public static void CountSort(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 1; i <array.length; i++) {
            if(array[i]>maxVal){
                maxVal=array[i];
            }
            if(array[i]<minVal){
                minVal=array[i];
            }
        }
        int len=maxVal-minVal+1;
        int[] count=new int[len];
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            count[index-minVal]++;
        }
        int j=0;
        for (int i = 0; i <count.length; i++) {
            while (count[i]!=0){
                array[j]=i+minVal;
                j++;
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={1,3,4,2,2,4,6,8,4,3,2,1};
        CountSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
